플로이드-워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구할 수 있는 알고리즘이다. (ㄷㄷ)
플로이드-워셜 알고리즘은 단계마다 '거쳐 가는 노드' 를 기준으로 알고리즘을 수행한다.

또한 정점의 개수가 V일 때, V 번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문에 DP 라고 볼 수 있다.

점화식은 다음과 같다.

즉, 기존에 저장된 거리보다 a 에서 k 로 가는 거리 + k 에서 b 로 가는 거리가 더 짧으면 갱신한다는 뜻이다.

수행 과정

주어진 그래프에 맞게 최단 거리 테이블을 갱신해둔다.
1 ~ N 번 정점을 거쳐가는 경우를 고려하여 테이블을 갱신한다.

코드

def floyd_warshall(n, dist):  
    for i in range(1, n + 1):  
        for a in range(1, n + 1):  
            for b in range(1, n + 1):  
                dist[a][b] = min(dist[a][b], dist[a][i] + dist[i][b])

주의할 점

정점의 개수가 V 일 때, V 번의 단계를 수행하면서 단계마다 O(V^2) 의 연산을 수행하여 현재 정점을 거쳐가는 모든 경로를 고려한다.

따라서 시간 복잡도가 O(V^3) 이므로 정점의 개수 값이 작을 경우에만 사용해야 한다.